#include <iostream>
#include <vector>
using namespace std;

class Solution {
	int tcnt = 1, qcnt = 1;
	vector<int> head, next, to, weight;
	vector<int> qhead, qnext, qto, qseq;
	vector<vector<int>> ecnt;
	vector<int> lca, vis;

	vector<int> father;
	vector<int> ans;

	int find(int x)
	{
		return x == father[x] ? x : father[x] = find(father[x]);
	}

	void addedge(int u, int v, int w)
	{
		next[tcnt] = head[u];
		to[tcnt] = v;
		weight[tcnt] = w;
		head[u] = tcnt++;
	}

	void addquest(int q, int p, int i)
	{
		qnext[qcnt] = qhead[q];
		qto[qcnt] = p;
		qseq[qcnt] = i;
		qhead[q] = qcnt++;
	}

	void dfs(int u, int f, int w)
	{
		vis[u] = 1;
		if (u == 0) {
			fill(ecnt[u].begin(), ecnt[u].end(), 0);
		} else {
			for (int i = 1; i <= 26; i++) {
				ecnt[u][i] = ecnt[f][i];
			}
			ecnt[u][w]++;
		}

		for (int e = head[u]; e; e = next[e]) {
			if (to[e] != f) {
				dfs(to[e], u, weight[e]);
				father[to[e]] = u;
			}
		}

		for (int q = qhead[u], p = qto[q]; q; q = qnext[q], p = qto[q]) {
			if (vis[p]) {
				lca[qseq[q]] = find(p);
			}
		}
	}

    public:
	vector<int> minOperationsQueries(int n, vector<vector<int>> &edges, vector<vector<int>> &queries)
	{
		int m = edges.size();
		int q = queries.size();
		head.resize(n, 0);
		next.resize((m << 1) + 1, 0);
		to.resize((m << 1) + 1, 0);
		weight.resize((m << 1) + 1, 0);

		for (int i = 0; i < edges.size(); i++) {
			addedge(edges[i][0], edges[i][1], edges[i][2]);
			addedge(edges[i][1], edges[i][0], edges[i][2]);
		}

		qhead.resize(n, 0);
		qnext.resize((q << 1) + 1, 0);
		qto.resize((q << 1) + 1, 0);
		qseq.resize((q << 1) + 1, 0);

		for (int i = 0; i < queries.size(); i++) {
			addquest(queries[i][0], queries[i][1], i);
			addquest(queries[i][1], queries[i][0], i);
		}

		father.resize(n, 0);
		vis.resize(n, 0);
		ans.resize(q, 0);
		lca.resize(q, 0);
		ecnt.resize(n + 1, vector<int>(27, 0));
		for (int i = 0; i < n; i++) {
			father[i] = i;
		}
		dfs(0, 0, 0);

		for (int i = 0, a, b, c, alledges; i < queries.size(); i++) {
			a = queries[i][0];
			b = queries[i][1];
			c = lca[i];

			int allcnt = 0;
			int maxcnt = 0;
			for (int i = 1, wcnt; i <= 26; i++) {
				wcnt = ecnt[a][i] + ecnt[b][i] - (ecnt[c][i] << 1);
				maxcnt = max(maxcnt, wcnt);
				allcnt += wcnt;
			}
			ans[i] = allcnt - maxcnt;
		}
		return ans;
	}
};

int main()
{
	// int n = 7;
	// vector<vector<int>> edges = {{0,1,1},{1,2,1},{2,3,1},{3,4,2},{4,5,2},{5,6,2}}, queries = {{0,3},{3,6},{2,6},{0,6}};
	int n = 8;
	vector<vector<int>> edges = {{1,2,6},{1,3,4},{2,4,6},{2,5,3},{3,6,6},{3,0,8},{7,0,2}}, queries = {{4,6},{0,4},{6,5},{7,4}};
	vector<int> ans = Solution().minOperationsQueries(n, edges, queries);
	for (auto v : ans) {
		cout << v << '\n';
	}

	return 0;
}